package 不同的子序列;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/19 10:18
 * @description:
 * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
 * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
 * 题目数据保证答案符合 32 位带符号整数范围。
 */
public class Solution {
    public int numDistinct(String s, String t) {
        // 找子序列出现的次数
        // ① dp数组及其下标含义：dp[i][j]表示t串中以下标 i-1 结尾的子串，s串中以下标 j-1 结尾的子序列，子串在子序列中出现的最大次数
        // ② 状态转移方程：如果当前字符相等，那么次数就等于不考虑当前两个字符的次数 + 不考虑s中这个字符但是考虑t中这个字符出现的次数
        //              如果当前字符不相等，那么次数就等于不考虑s字符，但是t字符任然是要考虑的
        //              dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
        //              dp[i][j] = dp[i][j - 1];
        // ③ dp数组的初始化：dp[0][i] = 1; 可以理解位t中取空串，那么在s中出现的次数就为1
        // ④ 遍历方向：从左上角到右下角


        int sLen = s.length();
        int tLen = t.length();

        int[][] dp = new int[tLen + 1][sLen + 1];
        for (int i = 0; i < sLen; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= tLen; i++) {
            for (int j = 1; j <= sLen; j++) {
                if (s.charAt(j - 1) == t.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }


        return dp[tLen][sLen];
    }
}
